package com.shm.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 *
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：lists = [[]]
 * 输出：[]
 *  
 *
 * 提示：
 *
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * @author SHM
 */
public class MergeKLists {
    /**
     * 方法二：两两合并有序链表
     * 受到「力扣」第 21 题（合并两个有序链表）的启发，或者是熟悉「归并排序」的话。不难想到，其实「合并」两个有序链表是相对容易的。
     *
     * 两个有序数组合并的做法是先把元素拷贝出来，再拷贝回去。而两个有序链表的合并，由于链表是动态的数据结构，可以很方便地更改结点指针的指向，可以通过 循环 和 递归 两种方式完成合并。
     *
     * 于是我们可以两两合并这些有序链表。
     * 复杂度分析：
     *
     * 时间复杂度：O(K^2N)O(K
     * 2
     *  N)，这里 NN 表示这 KK 个有序链表里最长的链表的长度，复杂度分析有一些繁琐，初学的时候可以暂时跳过。
     * 我们知道，合并两个有序链表（假设长度分别为 MM 和 NN）需要把两个链表的值都看一遍，时间复杂度为 O(M + N)O(M+N)。合并这 KK 个有序链表：
     *
     * 第 11 次合并后，链表的长度为 2N2N，合并的操作数是 N + N = 2NN+N=2N；
     *
     * 第 22 次合并后，链表的长度为 3N3N，合并的操作数是 2N + N = 3N2N+N=3N；
     * ...
     *
     * 第 K - 1K−1 次合并后，链表的长度为 KNKN，合并的操作数是 (K - 1)N + N = KN(K−1)N+N=KN；
     *
     * 综上所述：总的操作数是 2N + 3N + \dots + KN2N+3N+⋯+KN，通过等差数列的前 nn 项，我们不用具体计算数值，就知道，和的最高次项（系数化为 11）是 K^2NK
     * 2
     *  N，故时间复杂度为 O(K^2N)O(K
     * 2
     *  N)。
     *
     * 空间复杂度：O(1)O(1)，非递归的方式合并两个有序链表，使用的临时变量的个数为常数个。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/50nmuj/
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if(len==0){
            return null;
        }

        ListNode res = lists[0];
        for(int i=1;i<len;i++){
            if(lists[i]!=null){
                res= merge(res,lists[i]);
            }
        }
        return res;
    }

    ListNode merge(ListNode list1,ListNode list2){
        if(list1==null||list2==null){
            return list1==null?list2:list1;
        }
        ListNode dumy = new ListNode(-1);
        ListNode cur = dumy;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if(list1==null){
            cur.next = list2;
        }else{
            cur.next = list1;
        }

        return dumy.next;
    }


    /**
     * 方法二：分治合并
     * 思路
     *
     * 考虑优化方法一，用分治的方法进行合并。
     *
     * 将 kk 个链表配对并将同一对中的链表合并；
     * 第一轮合并以后， kk 个链表被合并成了 \frac{k}{2}
     * 2
     * k
     * ​
     *   个链表，平均长度为 \frac{2n}{k}
     * k
     * 2n
     * ​
     *  ，然后是 \frac{k}{4}
     * 4
     * k
     * ​
     *   个链表， \frac{k}{8}
     * 8
     * k
     * ​
     *   个链表等等；
     * 重复这一过程，直到我们得到了最终的有序链表。
     * 复杂度分析
     *
     * 时间复杂度：考虑递归「向上回升」的过程——第一轮合并 \frac{k}{2}
     * 2
     * k
     * ​
     *   组链表，每一组的时间代价是 O(2n)O(2n)；第二轮合并 \frac{k}{4}
     * 4
     * k
     * ​
     *   组链表，每一组的时间代价是 O(4n)O(4n)......所以总的时间代价是 O(\sum_{i = 1}^{\infty} \frac{k}{2^i} \times 2^i n) = O(kn \times \log k)O(∑
     * i=1
     * ∞
     * ​
     *
     * 2
     * i
     *
     * k
     * ​
     *  ×2
     * i
     *  n)=O(kn×logk)，故渐进时间复杂度为 O(kn \times \log k)O(kn×logk)。
     * 空间复杂度：递归会使用到 O(\log k)O(logk) 空间代价的栈空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
     * @param lists
     * @return
     */
    public ListNode mergeKLists_2(ListNode[] lists) {
        return  merge(lists,0,lists.length-1);
    }

    ListNode merge(ListNode[] lists,int l,int r){
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid = l+(r-l)/2;
        return merge(merge(lists,l,mid),merge(lists,mid+1,r));
    }

    /**
     * 方法四：优先队列（经典做法，必须掌握）
     * 事实上，将「合并两个有序链表」推广开来， KK 个有序链表合并的思路也不难得到。
     *
     * 每个链表头结点的元素的值很重要，只需要每一次选取 KK 个链表头结点中值最小的那个结点，将它归并回去即可；
     * 选取 KK 个链表头结点中值最小的那个结点，就需要使用「优先队列」，每一次选出头结点中数组最小的结点以后，这个结点的下一个结点（如果有的话），就成为当前链表的新的头结点，参与优先队列的值的比较，这显然是一个 动态选取最值 的过程，再一次说明「优先队列」是完成 KK 个链表合并的最合适的数据结构；
     * 由于链表是动态数组结构，可以直接在这 KK 个链表上进行操作。
     * 复杂度分析：
     *
     * 时间复杂度：O(N \log K)O(NlogK)，这里 NN 表示所有链表的结点总数（注意这里 NN 的含义与方法二、方法三不一样，与方法一一样），每一个链表结点都会在优先队列里进出一次，维护优先队列的时间复杂度为 O(\log K)O(logK)；
     * 空间复杂度：O(K)O(K)，优先队列的大小为 KK，故空间复杂度为 O(K)O(K)。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/50nmuj/
     * @param lists
     * @return
     */
    public ListNode mergeKLists_3(ListNode[] lists) {
        int len = lists.length;
        if(len==0){
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for (ListNode list : lists) {
            if (list!=null) {
                minHeap.offer(list);
            }
        }

        ListNode dumy = new ListNode(-1);
        ListNode cur = dumy;
        // 注意：这里我们选择的操作是先从优先队列里拿出最小的元素，然后再添加
        // 事实上，如果优先队列有提供 replace 操作，应该优先选择 replace
        while (!minHeap.isEmpty()){
            ListNode node = minHeap.poll();
            cur.next = node;
            if(node.next!=null){
                minHeap.offer(node.next);
            }
            cur = cur.next;
        }
        return dumy.next;
    }
}

//import java.util.Comparator;
//补充：这里给出一版使用我们自己实现的堆完成的操作，弥补了 Java 的 java.util.PriorityQueue 类中没有 replace() 方法。 仅作为练习。

//作者：liweiwei1419
//链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/50nmuj/
//优先队列的高效实现是堆，堆是一个完全二叉树，因此 可以存储在数组里，并且父亲结点和孩子结点可以很方便地互相访问；
/*使用数组表示完全二叉树（重要）
        完全二叉树有个重要的性质：它 可以使用数组表示。这是因为按照从上至下、从左至右的顺序给完全二叉树编号，任意结点的父亲结点和子结点的下标是有规律的。这一点决定了，在完全二叉树中，左右子结点、父结点可以根据当前下标数值 互相访问：

        根据父亲结点的下标，可以访问到它的两个子结点；
        根据子结点的下标，可以访问到它的唯一的父亲结点。
        使用数组存放二叉树的优点是：不用维护左右子结点、父结点的引用关系。这是因为如果我们给二叉树的结点的顺序编号，就不难发现它们的规律。

        作者：liweiwei1419
        链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/50rqgc/
 */
class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }

        // Comparator.comparingInt(o -> o.val) 这样写表示最小堆
        // Comparator.comparingInt(o -> -o.val) 这样写表示最大堆
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(len, Comparator.comparingInt(o -> o.val));
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        while (!minHeap.isEmpty()) {
            // 先看一眼，并不取出
            ListNode top = minHeap.peek();
            curNode.next = top;
            curNode = curNode.next;

            if (top.next == null) {
                // 只有在当前结点是链表的最后一个结点的时候，才取出
                minHeap.poll();
            } else {
                // 否则执行 replace 操作
                minHeap.replace(top.next);
            }
        }
        return dummyNode.next;
    }

    public class PriorityQueue<T> {

        private T[] data;

        private Comparator<T> cmp;

        private int capacity;

        private int size;

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public T peek() {
            if (isEmpty()) {
                throw new IllegalArgumentException("堆为空。");
            }
            // 下标 0 不存元素
            return data[1];
        }

        public PriorityQueue(int capacity, Comparator<T> cmp) {
            this.cmp = cmp;
            data = (T[]) new Object[capacity + 1];
            this.capacity = capacity;
            size = 0;
        }

        public void offer(T item) {
            if (size + 1 > capacity) {
                throw new IllegalArgumentException("堆空间已满。");
            }

            // 把新添加的元素放在数组的最后一位
            data[size + 1] = item;
            // 维护 size 的定义
            size++;
            // 考虑将 data[size] 元素上移到合适的位置
            siftUp(size);
        }

        private void swap(T[] data, int index1, int index2) {
            T temp = data[index1];
            data[index1] = data[index2];
            data[index2] = temp;
        }

        private void siftUp(int k) {
            T temp = data[k];
            while (k > 1) {
                if (cmp.compare(data[k / 2], temp) > 0) {
                    data[k] = data[k / 2];
                    k /= 2;
                } else {
                    break;
                }
            }
            data[k] = temp;
        }

        public T poll() {
            if (size == 0) {
                throw new IllegalArgumentException("堆为空。");
            }
            T ret = data[1];
            // 把最后一个元素的值赋值到二叉堆的根结点
            data[1] = data[size];
            size--;
            siftDown(1);
            return ret;
        }

        private void siftDown(int k) {
            // 编写方式等价于「插入排序」的优化，先暂存，再逐个移动，最后空出位置把先前暂存元素放进去
            T temp = data[k];
            while (2 * k <= size) {
                int j = 2 * k;
                if (j + 1 <= size && cmp.compare(data[j + 1], data[j]) < 0) {
                    j++;
                }
                if (cmp.compare(temp, data[j]) <= 0) {
                    break;
                }
                data[k] = data[j];
                k = j;
            }
            data[k] = temp;
        }

        public void replace(T item) {
            if (isEmpty()) {
                throw new IllegalArgumentException("堆为空。");
            }
            // 注意：堆顶元素替换，size 不变
            data[1] = item;
            siftDown(1);
        }
    }
}